The present invention relates to industrial control systems and the like and in particular to an industrial control system comprised of many distributed controllers dividing job tasks among themselves using xe2x80x9cmarket modelxe2x80x9d based bids and counter bids.
In a centralized model for industrial control, a single central controller (being a specialized computer) coordinates all aspects of the controlled process. Input signals representing values from sensors on the controlled process are communicated to the central controller which executes a control program to develop output signals which are communicated to actuators on the controlled process.
The centralized model is conceptually simple and requires programming only a single device. Nevertheless, the centralized model has some disadvantages. Control systems using this model are particularly vulnerable to failure of the single central controller. Further, communication of all I/O signals to a central location and executing the control program on a single computer, particularly for large control systems, can place undue burdens on processing resources and communication bandwidth.
In the distributed model for industrial control, the control program is executed by a number of spatially separate controllers intercommunicating only as needed on a common network. By placing these controllers near relevant I/O points, the communication of large amounts of I/O data is diminished. Having multiple control devices can also reduce the susceptibility of the control system to failure of any one device.
One difficulty with distributed control is that of developing the multiple control programs to dividing the control tasks among the various distributed controllers and coordinating their actions. One promising method of both dividing the control task among the controllers and coordinating their actions borrows from a market model of the economy in which many different autonomous individuals organize themselves (through bidding and counter bidding) to produce complex products or services without central control. In such autonomous cooperative systems (ACS), a job description is presented to a large number of autonomous cooperative units (ACUs), which, based on knowledge of their own capabilities and limitations, bid on portions of the job and counter bid in response to requests for bids. Control programs are simply developed and the potential exists for control programs to be quickly changed as new circumstances develop. Examples of this would be if it is desired to produce a new product or if ACUs (and associated equipment) are introduced or removed from the system. A description of some such of autonomous control systems are described in co-pending patents.
For an autonomous cooperative system to produce an optimized outcome, it is desirable that many different of divisions of the job among the ACUs be explored and thus that a large number of bids be collected from many different ACUs. This is done by allowing each ACU to make multiple simultaneous requests for bids from other ACUs. It follows that a single ACUs may receive multiple requests for bids from multiple other ACUs each of which must be considered in a separate xe2x80x9ccontextxe2x80x9d and each of which may mature into a different completed bid.
The bidding process for each context requires a large number of bidding messages be transmitted over the network 16. Such messages generally include xe2x80x9cbid requestsxe2x80x9d and replies to bid requests including xe2x80x9cbid successxe2x80x9d, xe2x80x9cbid failurexe2x80x9d and xe2x80x9ccounter bidxe2x80x9d messages. The numbers of messages increases geometrically with the number of ACUs involved and these messages can easily overtax even high-speed communication networks thus delaying the determination of a control solution. This delay limits the usefulness of an ACS in responding quickly to changing control situations and effectively limits the size of control problems that may be advantageously handled by the ACS.
What is needed is a way to realize a freely scalable ACS system that may rapidly determine an optimized control solution that may be implemented with existing hardware having network bandwidth and processing limitations.
The present invention allows complex, multi-context bids combinations to be freely explored by an ACS while still obtaining bid closure within an acceptable time. This is done by attaching a bid response time to each top-level bid. As sub-bids are propagated, they take this bid response time and subtract an amount related to their processing time, and forward that to other bidding partners. Bidding stops when the bid response time (as successively modified) is insufficient for further sub-bids.
As an adjunct to the goal of allowing bid solution space to be freely explored, the present invention also significantly reduces the number of bid messages needed to provide a solution, and thus requires less network bandwidth and ACU processing power. This is done by reporting to each ACU that was part of a successful bid together with the information about the sub-bidding partner of that ACU. In future bidding situations, the given ACU preferentially bids with those sub-bidding partners that were earlier part of a successful bid.
Specifically then, the present invention provides an apparatus for and method of coordinating a plurality of autonomous control units (ACUs) to control associated equipment. In a first step, a given ACU receives from a prior ACU a description of at least a portion of a job to be bid upon, together with a given bid response time limit after which a bid will not be accepted by the prior ACU. When a primary part of the job portion matches the capabilities of the given ACU, that ACU communicates a secondary part of the job portion not matching the capabilities of the given ACU over a network to at least one subsequent ACU together with a subsequent bid response time less than the given bid response time limit after which a bid will not be accepted by the given ACU. These steps are repeated with the subsequent ACU acting as the given ACU and a new ACU acting as the subsequent ACU.
Thus it is one object of the invention provide a predictable time limit to the bidding process that is compatible with the decentralized nature of the bidding system. The time limit of the bid response time may be passed along with each bid request to close all bids without the intervention of a central controller.
The subsequent bid response time may equal the given bid response time minus the time required by the given ACU to process the second part of the job for further communication over the network.
Thus it is another object of the invention to allow the sub-bidding process to continue to the last possible moment after which sub-bids could not be collected into a completed bid.
When a primary part of the job portion does not match the capabilities of the given ACU, the secondary part is not communicated to the subsequent ACU and a bid failure message is communicated to the prior ACU.
Thus it is another object of the invention to terminate bid message traffic on all chains that will be unsuccessful even if the time limit has not been exceeded.
The given ACU may receive, from at least one prior ACU a first and second description of at least a first and second different job portion with associated first and second given bid response times after which bids will not be accepted by the prior ACU. In this case, the given ACU may identify a primary part of the first and second job portion each matching the capabilities of the given ACU and a secondary part of the first and second job portions not matching the capability of the ACU. The given ACU may then communicate a description of the first and second secondary part of the first and second job portions over the network to at least two subsequent ACUs together with a third and fourth subsequent bid response time limit less than the given first and second bid response times, respectively.
Thus it is another object of the invention to provide a mechanism for bid closure after a predetermined time that is compatible with a multi-context bidding process.
In response to the communicated secondary part of the job portion, the given ACU may receive within the given bid response time at least one reply bid message from a subsequent ACU, the reply bid message being any of:
(i) bid success messages, indicating that the secondary part of the job portion matches the capability of a subsequent ACU,
(ii) bid failure messages indicating that the secondary part of the job portion does not match the capability of a subsequent ACU; and
(iii) a bid modification message indicating that the secondary part of the job portion might match the capability of a subsequent ACU with some modification of the secondary part of the job description.
When the reply includes at least one bid success message, the given ACU may forward to the prior ACU only the bid success messages. Alternatively, when the reply includes no bid success messages but at least one bid modification message, the given ACU may forward to the prior ACU only the bid modification messages. Finally, when the reply includes no bid success messages and no bid modification messages, but at least one bid failure message, the given ACU may forward to the prior ACU only the bid failure messages.
Thus it is another object of the invention to minimize network traffic by filtering bid response to only the best bid responses at each ACU.
The method may include the step of reporting a bid success from the given ACU to the initial ACU for the primary part of the job. Further the invention may identify at an initial ACU successful ACUs being part of a sequence of ACUs reporting bid successes for the complete job and communicate to each of the successful ACUs the identity of ACUs subsequent to the successful ACU in the sequence. From that point on, the given ACU may communicate preferentially with subsequent ACUs identified as being part of a sequence of ACUs previously reporting bid successes.
Thus it is another object of the invention to direct bids to those other ACUs which will likely respond successfully in a sub-bid and thereby further reduce network traffic.
The foregoing and other objects and advantages of the invention will appear from the following description. In this description, reference is made to the accompanying drawings, which form a part hereof, and in which there is shown by way of illustration, a preferred embodiment of the invention. Such embodiment and its particular objects and advantages do not define the scope of the invention, however, and reference must be made therefore to the claims for interpreting the scope of the invention.